package day40_401;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/18 19:48
 * @Version 1.0
 */
public class Solution {

    int[] hours = new int[]{1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
    int[] minutes = new int[]{0, 0, 0, 0, 1, 2, 4, 8, 16, 32};
    List<String> res = new ArrayList<>();

    public List<String> readBinaryWatch(int turnedOn) {
        backtrack(turnedOn, 0, 0, 0);
        return res;

    }
    // 回溯的参数：num(需要点亮的灯，初始为turnedOn),index(点亮的下标)
    // hour(小时数)minute(分钟数)
    private void backtrack(int num, int index, int hour, int minute) {
        if (hour > 11 || minute > 59) return;
        // 递归出口,当点亮到第0栈灯的时候，那么回溯所有数据
        if (num == 0) {
            // 进行字符串拼接
            StringBuilder sb = new StringBuilder();
            sb.append(hour).append(":");
            if (minute < 10) {
                sb.append("0");
            }
            sb.append(minute);
            res.add(sb.toString());
            //记得return终止掉
            return;
        }
        // 这里是从下标开始递归遍历
        for (int i = index; i < 10; i++) {
            backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i]);
        }
    }
}
